Tiền thân của Binh đoàn là Binh đoàn Mississippi, vốn bị đánh bại trong trận Shiloh và Perryville. Trên cơ sở các đơn vị cũ còn lại của Binh đoàn Mississippi, Binh đoàn Tennessee được thành lập ngày 20 tháng 11 năm 1862[1]. Một vị chỉ huy mới được bổ nhiệm làm chỉ huy binh đoàn là Đại tướng Braxton Bragg. Ông đã nhanh chóng củng cố lại lực lượng và đã chỉ huy binh đoàn đánh bại Binh đoàn Cumberland của quân Liên bang miền Bắc, do Thiếu tướng William Rosecrans chỉ huy, trong trận Stones River vào ngày 31 tháng 12 năm 1862. Tuy thắng trận, Bragg vẫn phải rút khỏi Murfreesboro và tập hợp lực lượng ở Tullahoma để tiếp tục củng cố binh đoàn.

Mùa hè năm 1863, tướng Rosecrans đã mở một cuộc phản công trở lại vào Binh đoàn Tennessee, thường được biết đến với tên gọi Chiến dịch Tullahoma. Binh đoàn của Bragg buộc phải rút về miền bắc Georgia, bỏ các trung tâm đường sắt quan trọng của Chattanooga. Tuy nhiên, sau khi được tiếp viện bởi lực lượng của Quân đoàn I, Binh đoàn Bắc Virginia, do Trung tướng James Longstreet chỉ huy, Binh đoàn Tennessee đã đánh thiệt hại đáng kể cho lực lượng của Rosecrans tại trận Chickamauga vào tháng 9 năm 1863.

Sau trận Chickamauga, Binh đoàn Tennessee đã bao vây các lực lượng quân Liên bang tại Chattanooga, sau khi đã chiếm vị trí phòng thủ trên các ngọn đồi xung quanh thành phố. Tuy nhiên, ngay sau đó, Binh đoàn Cumberland đã được tiếp viện thêm bởi lực lượng của Thiếu tướng Ulysses S. Grant, từ Binh đoàn sông Tennessee, cùng với hai quân đoàn từ Binh đoàn Potomac, do Thiếu tướng Joseph Hooker chỉ huy, đặt dưới quyền tổng chỉ huy của Grant thay cho Rosecrans. Ngược lại, Bragg lại phải gửi lực lượng của tướng Longstreet và gần như tất cả các kỵ binh của mình đi cứu viện cho Knoxville, làm giảm sức mạnh của binh đoàn. Quân Liên bang dễ dàng áp đảo binh đoàn của Bragg trong trận Missionary Ridge vào ngày 25 tháng 11 năm 1863, buộc Bragg bỏ cuộc vây hãm Chattanooga, chiếm lại miền bắc Georgia.

Sau thất bại đó, Bragg đã được thay thế trong chức vụ chỉ huy Binh đoàn Tennessee bởi tướng Joseph E. Johnston, cựu chỉ huy trưởng Binh đoàn Bắc Virginia. Trong Chiến dịch Atlanta năm 1864, Johnston phải đối đầu với lực lượng Liên bang do Thiếu tướng William T. Sherman chỉ huy, người đặt ra mục tiêu quan trọng là tiêu diệt Binh đoàn Tennessee và sau đó chiếm lại Atlanta. Johnston, người chủ trương bảo tồn lực lượng hơn là bảo vệ lãnh thổ, đã thiên về xu hướng tránh các cuộc đụng độ với Sherman, nên đã thực hiện một loạt cuộc hành quân làm thất bại ý đồ đánh bại Binh đoàn Tennessee trong một trận quyết định của tướng Sherman. Tuy nhiên, điều này đã gây nên sự không hai lòng của một số nhà lãnh đạo thiếu kiên nhẫn của Liên minh miền Nam tại Richmond, đặc biệt là Tổng thống miền Nam Jefferson Davis, người vốn không có ấn tượng tốt với Johnston. Sau trận tập kích vào sườn cánh quân của Sherman Johnston tại sông Chattahoochee, Binh đoàn Tennessee trở lại Atlanta, Johnston đã bị thay thế bởi Trung tướng John Bell Hood.

Hood tỏ ra là một chỉ huy kém năng lực. Sau nhiều nỗ lực không thành công nhằm công kích lực lượng của Sherman nhằm dỡ bỏ áp lực lên Atlanta, thành phố rơi vào tay quân Liên bang ngày 2 tháng 9 năm 1864. Thay vì tiếp tục chiến thuật của Johnston là tránh nghênh chiến trực diện nhưng buộc quân Sherman phải di chuyển, Hood bây giờ lại chuyển quân về phía tây và phía bắc Tennessee, cho phép Sherman tự do chuyển quân ở phía nam để thực hiện cuộc Hành quân ra biển. Hood cho rằng, khi đấy ông có thể rảnh tay để có để nghênh chiến với đối thủ cũ là Binh đoàn Cumberland, lúc này do Thiếu tướng George H. Thomas chỉ huy, cũng như Binh đoàn Ohio, do Thiếu tướng John Schofield chỉ huy.

Vào ngày 30 tháng 11 năm 1864, Hood tấn công vào lực lượng yếu hơn là cánh quân nhỏ do tướng Schofield chỉ huy trong trận Franklin. Tuy thiệt hại đến một phần tư quân số, ông vẫn cố tiếp tục tiến lên phía bắc vào trung tâm Tennessee và tiến hành vây hãm Nashville. Ngày 15 tháng 12, Thomas tham chiến, tập kích vào phía sau lưng quân miền Nam khi đang xây dựng tuyến vây hãm Nashville. Binh đoàn Tennessee bị vỡ trận và bị quân Liên bang truy kích liên tục. Khi các lực lượng còn lại của Binh đoàn Tennessee có thể tập hợp lại ở Tupelo ngay trước năm mới, lực lượng của nó đã bị tổn thất nặng nến đến 3/4 kể từ khi Hood nắm quyền chỉ huy.

Hood từ chức vào tháng 1 năm 1865, và trong những tháng cuối cùng của chiến tranh, tướng Joseph E. Johnston đã được phục hồi chức vụ chỉ huy những gì còn lại của Binh đoàn Tennessee và đội quân nhỏ khác trong việc phòng thủ vô vọng chống lại lực lượng của Sherman hành quân qua Carolina. Ngày 26 tháng 4 năm 1865, Binh đoàn Tennessee đầu hàng quân miền Bắc tại Bennett Place, gần Durham Station, Bắc Carolina.